package com.wdc.hashtable;

import java.util.Arrays;

public class ShellSort {
    public static void sort(int[] a){
        for( int gap = a.length >> 1; gap >= 1; gap = gap >> 1){
            for (int low = gap; low < a.length; low++) {
                int t = a[low];
                int i = low -gap;
                //从右向左找出待插入位置，空出来
                while (i >= 0 && a[i] >t ){
                    a[i+gap] = a[i];
                    i-= gap;
                }

                //找到待插入位置
                if (i != low -gap){
                    a[i+gap] = t;
                }

            }
        }

    }

    public static void main(String[] args) {
        int[] a ={2,1,7,4,9,4,99};
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}
